package qsc.algorithm.pack;

/**
 * @auther QiuShangcheng
 * @create 2021/4/15
 */
public class manyPack {
    public static void main(String[] args) {
        int[] weight = {1,4,3};
        int[] val = {1500,3000,2000};
        int[] num = {3,1,1};
        int i = manyPack(4, 3, weight, val,num);
        System.out.println(i);
    }

    /**
     *多重背包（动态规划算法）
     *
     * @param V 背包总容量
     * @param N 物品种类
     * @param weight 物品重量
     * @param val 物品价值
     * @param num 物品数目
     * @return
     */
    public static int manyPack(int V, int N, int[] weight, int[] val, int[] num){
        //初始化状态转移数组
        int[][] dp = new int[N+1][V+1];
        for (int i = 1; i < N + 1; i++){
            for (int j = 1;j < V + 1;j ++){
                //如果当前背包容量j小于当前第i个物品的总量weight[i-1]
                if (weight[i-1] > j){
                    //则上一次的最大价值仍适用当前
                    dp[i][j] = dp[i-1][j];
                }else {//则上一次的最大价值不适用当前，需要重新规划
                    //找到当前容量下背包最多能放几个i物品
                    int maxNum = Math.min(j/weight[i-1],num[i-1]);
                    //找出当前状态下最大价值
                    for (int  curNum= 1; curNum<maxNum+1; curNum++){
                      dp[i][j] = Math.max(dp[i-1][j],curNum*val[i-1]+dp[i-1][j-curNum*weight[i-1]]);
                    }
                }
            }
        }
        return dp[N][V];
    }
}
